package com.data.basic.chapter09.leetcode;

/**
 * leetcode 307
 */
class NumArray3 {

    private int[] data;

    private int sum[];//sum[i] 存储前i个元素和，sum[0]=0而不是第0个元素
    //sum[i]存储 nums [0...i-1] 的和

    public NumArray3(int[] nums) {

        data = new int[nums.length];
        for (int i=0;i<nums.length;i++){
            data[i] = nums[i];
        }


        sum = new int[nums.length+1];
        sum[0]=0;
        for (int i=1;i<sum.length;i++){
            sum[i]+=sum[i-1]+nums[i-1];
        }
    }

    public void update(int i, int val) {
        data[i] = val;
        for (int j=i+1;j<sum.length;j++){
            sum[j] = sum[j-1]+data[j-1];
        }

    }

    public int sumRange(int i, int j) {
        return sum[j+1]-sum[i];
    }
}